class Node {
    constructor(key) {
        this.key = key;
        this.left = null;
        this.right = null
    }
}
export class BinarySearchTree {
    constructor() {
        this.root = null;
    }
    // insert:向树中插入一个新的键
    insert(key) {
        // 1.根据key创建Node节点
        let newNode = new Node(key)
        // 2.如果原来的树是一棵空树
        if (!this.root) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode)
        }
    }
    // 递归循环查找节点
    insertNode(node, newNode) {
        if (newNode.key > node.key) {
            // 如果插入内容比当前节点内容大, 往右插         
            if (!node.right) {
                // 如果右节点没有内容直接插入
                node.right = newNode;
            } else {
                // 如果有内容就递归进入右边节点继续判断
                this.insertNode(node.right, newNode);
            }
        } else {
            // 如果插入内容比当前节点内容大, 往左插         
            if (!node.left) {
                // 如果左节点没有内容直接插入
                node.left = newNode;
            } else {
                // 如果有内容就递归进入左边节点继续判断
                this.insertNode(node.left, newNode)
            }
        }
    }
    // preOrderTraverse:通过先序遍历方式遍历所有节点
    preOrderTraverse() {
        this.preOrderTraverseNode(this.root);
    }
    // 先序遍历递归遍历
    preOrderTraverseNode(node) {
        if (!node) return
        // 先左后右
        console.log(node.key);
        this.preOrderTraverseNode(node.left);
        this.preOrderTraverseNode(node.right);
    }
    // inOrderTraverse:通过中序遍历方式遍历所有节点
    inOrderTraverse() {
        this.inOrderTraverseNode(this.root)
    }
    // 中序遍历递归遍历
    inOrderTraverseNode(node) {
        if (!node) return
        // 先左后右
        this.inOrderTraverseNode(node.left);
        console.log(node.key);
        this.inOrderTraverseNode(node.right);
    }
    // postOrderTraverse:通过后序遍历方式遍历所有节点
    postOrderTraverse() {
        this.postOrderTraverseNode(this.root)
    }
    // 后序遍历递归遍历
    postOrderTraverseNode(node) {
        if (!node) return
        // 先左后右
        this.postOrderTraverseNode(node.left);
        this.postOrderTraverseNode(node.right);
        console.log(node.key);
    }
    // min:返回树中最小的值/键
    min() {
        let node = this.root
        // 一直循环最左边
        while (node.left !== null) {
            node = node.left
        }
        return node.key
    }
    // max:返回树中最大的值/键
    max() {
        let node = this.root
        // 一直循环最右边
        while (node.right) {
            node = node.right
        }
        return node.key
    }
    // search:在树中查找一个键,如果节点存在,则返回tree;如果不存在,则返回false
    search(key) {
        // 1.判断node有没有值

        // 2.判断搜索的key和节点值的关系

    }
    // remove:从树中移除某个键
    remove(key) {

    }
}